import java.util.Arrays;

public class MyPriorityQueue {
    //成员变量：1.数组的引用指向储存元素的数组2.usedSize记录数组存储的有效元素个数
    public int[] elem;
    public int usedSize;

    //默认不带参数的构造方法
    public MyPriorityQueue(){
        this.elem=new int[10];
    }

    //利用给定数组初始化的方法
    public void init(int[]array){
        //数组存储大小不够则扩容
        while(elem.length<array.length){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        for(int i=0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }

    }

    //创建大根堆时调用到的向下调整的底层方法
    private void maxSiftDown(int parent,int end){
        //默认子女中的最大值为左子女
        int child=2*parent+1;
        while(child<end){
            //判断右子女是否为二者中最大值
            if(child+1<end){
                if(elem[child]<elem[child+1]){
                    child++;
                }
            }
            if(elem[parent]<elem[child]){
                //子女节点中最大值大于双亲则进行交换调整
                int temp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=temp;
                //向下迭代
                parent=child;
                child=2*parent+1;
            }else{
                //子女节点中最大值小于双亲说明该树已经为大根堆，无需向下调整，直接中断即可
                break;
            }
        }
    }

    //创建一个大根堆的方法
    public void createMaxHeap(){
        //从最后一棵子树倒序调整
        for(int parent=((usedSize-1-1)/2);parent>=0;parent--){
            //调用向下调整的底层方法
            maxSiftDown(parent,usedSize);
        }
    }

    //创建小根堆时调用到的向下调整的底层方法
    private void minSiftDown(int parent,int end){
        //默认子女中的最小值为左子女
        int child=2*parent+1;
        while(child<end){
            //判断右子女是否为二者中最小值
            if(child+1<end){
                if(elem[child]>elem[child+1]){
                    child++;
                }
            }
            if(elem[parent]>elem[child]){
                //子女节点中最小值小于双亲则进行交换调整
                int temp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=temp;
                //向下迭代
                parent=child;
                child=2*parent+1;
            }else{
                //子女节点中最小值大于双亲说明该树已经为小根堆，无需向下调整，直接中断即可
                break;
            }
        }
    }

    //创建一个小根堆的方法
    public void createMinHeap(){
        //从最后一棵子树倒序调整
        for(int parent=((usedSize-1-1)/2);parent>=0;parent--){
            //调用向下调整的底层方法
            minSiftDown(parent,usedSize);
        }
    }

    //插入元素时用到的底层判满方法
    private boolean isFull(){
        return elem.length==usedSize;
    }

    //大根堆插入元素时调用到的向上调整的底层方法
    private void maxSiftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            //如果子女节点的值大于双亲节点的值则进行交换调整
            if(elem[child]>elem[parent]){
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                //向上迭代
                child=parent;
                parent=(child-1)/2;
            }else {
                //子女节点小于双亲说明该树已经为大根堆，无需向下调整，直接中断即可
                break;
            }
        }
    }

    //大根堆插入元素的方法
    public void maxOffer(int val){
        //判满扩容
        if(isFull()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        //将插入的元素放置在数组末端
        elem[usedSize]=val;
        usedSize++;
        //调用到向上调整的底层方法
        maxSiftUp(usedSize-1);
    }

    //小根堆插入元素时调用到的向上调整的底层方法
    private void minSiftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            //如果子女节点的值小于双亲节点的值则进行交换调整
            if(elem[child]<elem[parent]){
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                //向上迭代
                child=parent;
                parent=(child-1)/2;
            }else {
                //子女节点大于双亲说明该树已经为小根堆，无需向下调整，直接中断即可
                break;
            }
        }
    }

    //小根堆插入元素的方法
    public void minOffer(int val){
        //判满扩容
        if(isFull()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        //将插入的元素放置在数组末端
        elem[usedSize]=val;
        usedSize++;
        //调用到向上调整的底层方法
        minSiftUp(usedSize-1);
    }

    //删除元素时用到的底层判空方法
    private boolean isEmpty(){
        return usedSize==0;
    }

    //大根堆删除元素的方法
    public int maxPoll(){
        //判空返回-1
        if(isEmpty()){
            return -1;
        }
        //将队头元素取出
        int val=elem[0];
        //队头与队尾元素互换
        int temp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=elem[0];
        //将usedSize--使得队尾元素（交换前的队头元素）被踢出维护范围即可实现删除
        usedSize--;
        //此时只有完全二叉树的根节点不为大根堆，调用向下调整的方法进行调整即可
        maxSiftDown(0,usedSize);
        return val;
    }

    //小根堆删除元素的方法
    public int minPoll(){
        //判空返回-1
        if(isEmpty()){
            return -1;
        }
        //将队头元素取出
        int val=elem[0];
        //队头与队尾元素互换
        int temp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=elem[0];
        //将usedSize--使得队尾元素（交换前的队头元素）被踢出维护范围即可实现删除
        usedSize--;
        //此时只有完全二叉树的根节点不为小根堆，调用向下调整的方法进行调整即可
        minSiftDown(0,usedSize);
        return val;
    }

    //获取队头元素的方法
    public int peek(){
        return elem[0];
    }

    //展示数组元素的方法
    public  void display(){
        System.out.println(Arrays.toString(elem));
    }
}